#include <bits/stdc++.h>

typedef struct node
{
	int value;
	struct node *next;
} *NODE;

NODE hasheadTailCreate(NODE head, int values[], int valCnt)
{
	NODE curNode = head;
	for (int index = 0; index < valCnt; index++)
	{
		NODE newNode = (NODE)malloc(sizeof(NODE));
		newNode->value = values[index];
		newNode->next = NULL;
		curNode->next = newNode;
		curNode = curNode->next;
	}
	return head;
}

NODE noheadTailCreate(int values[], int valCnt)
{
	NODE head = (NODE)malloc(sizeof(NODE));
	head->next = NULL;
	head->value = 0;
	NODE curNode = head;
	for (int index = 0; index < valCnt; index++)
	{
		NODE newNode = (NODE)malloc(sizeof(NODE));
		newNode->value = values[index];
		newNode->next = NULL;
		curNode->next = newNode;
		curNode = curNode->next;
	}
	return head;
}

NODE hasheadHeadCreate(NODE head, int values[], int valCnt)
{
	for (int index = 0; index < valCnt; index++)
	{
		NODE newNode = (NODE)malloc(sizeof(NODE));
		newNode->value = values[index];
		newNode->next = head->next;
		head->next = newNode;
	}
	return head;
}

NODE noheadHeadCreate(int values[], int valCnt)
{
	NODE head = (NODE)malloc(sizeof(NODE));
	head->next = NULL;
	head->value = 0;
	for (int index = 0; index < valCnt; index++)
	{
		NODE newNode = (NODE)malloc(sizeof(NODE));
		newNode->value = values[index];
		newNode->next = head->next;
		head->next = newNode;
	}
	return head;
}

void interationLinkedList(NODE head)
{
	while (head != NULL)
	{
		printf("%d ", head->value);
		head = head->next;
	}
	printf("\n");
}

NODE searchLinkedList(NODE head, int value)
{
	while (head != NULL)
	{
		if (head->value == value)
		{
			printf("Find the node successfully! The value is %d\n", head->value);
			return head;
		}
		head = head->next;
	}
	printf("Can't find the node!\n");
	return NULL;
}

void delLinkedList(NODE head, int value)
{
	if (head->value == value)
	{
		NODE delNode = head;
		head = head->next;
		free(delNode);
	}
	while (head->next != NULL)
	{
		if (head->next->value == value)
		{
			NODE delNode = head->next;
			head->next = head->next->next;
			free(delNode);
			printf("Delete the node successfully!\n");
			return;
		}
		head = head->next;
	}
	printf("Can't find the node!\n");
}

void insertLinkedList(NODE head, int beInsertedValue, int insertedValue)
{
	while (head != NULL)
	{
		if (head->value == beInsertedValue)
		{
			NODE insertedNode = (NODE)malloc(sizeof(NODE));
			insertedNode->value = insertedValue;
			insertedNode->next = head->next;
			head->next = insertedNode;
			printf("Insert the node successfully!\n");
			return;
		}
		head = head->next;
	}
	printf("Can't find the node!\n");
}

NODE reverseLinkedList(NODE head)
{
	NODE preNode = head;
	NODE nextNode = head->next;
	head->next = NULL;
	while (nextNode != NULL)
	{
		NODE tempNode = nextNode->next;
		nextNode->next = preNode;
		preNode = nextNode;
		nextNode = tempNode;
	}
	return preNode;
}

int main()
{
	const int valCnt = 6;
	int values[valCnt] = {1, 2, 3, 4, 5, 6};

	NODE head1 = (NODE)malloc(sizeof(NODE));
	head1->next = NULL;
	head1->value = 0;
	head1 = hasheadTailCreate(head1, values, valCnt);
	interationLinkedList(head1);

	NODE head2 = (NODE)malloc(sizeof(NODE));
	head2->next = NULL;
	head2->value = 0;
	head2 = hasheadHeadCreate(head2, values, valCnt);
	interationLinkedList(head2);

	NODE head3 = noheadTailCreate(values, valCnt);
	interationLinkedList(head3);

	NODE head4 = noheadHeadCreate(values, valCnt);
	interationLinkedList(head4);

	searchLinkedList(head1, 4);

	delLinkedList(head1, 4);
	interationLinkedList(head1);

	insertLinkedList(head1, 3, 4);
	interationLinkedList(head1);

	head1 = reverseLinkedList(head1);
	interationLinkedList(head1);
	return 0;
}
